package com.github.yangyishe.p100;

import java.util.Arrays;

/**
 * 75. 颜色分类
 * https://leetcode.cn/problems/sort-colors/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 *
 * 必须在不使用库内置的 sort 函数的情况下解决这个问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [2,0,2,1,1,0]
 * 输出：[0,0,1,1,2,2]
 * 示例 2：
 *
 * 输入：nums = [2,0,1]
 * 输出：[0,1,2]
 *
 *
 * 提示：
 *
 * n == nums.length
 * 1 <= n <= 300
 * nums[i] 为 0、1 或 2
 *
 *
 * 进阶：
 *
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 */
public class Problem75 {
    public static void main(String[] args) {
        int[] nums=new int[]{2,0,2,1,1,0};

        Problem75 problem75 = new Problem75();
        problem75.sortColors(nums);
        System.out.println("Arrays.toString(nums) = " + Arrays.toString(nums));
    }

    /**
     * 思路：
     * 普通模式过于简单，此处仅考虑进阶模式——一趟扫描
     * 从开始遍历，遇到0从不动，遇到2则与尾部元素交换，同时尾部指针-1，遇到1则慢指针记录此处，直到又遇到0，再与该元素指针交换。
     * 换言之，维护3个指针处理好其中的关系，是一趟走完的快捷方式
     *
     * 思路确定后，就是凑
     * 此处确实还是容易乱，暂时也没找出可供总结的规律
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        int p0=0;
        int p1=0;
        int p2=nums.length-1;

        while(p1<p2){

            if(nums[p0]==0){
                if(p1==p0){
                    p0++;
                    p1++;
                }else{
                    cas(nums,p1,p0);
                    p1++;
                }
            }else if(nums[p0]==1){
                p0++;
            }else{
                cas(nums,p0,p2);
                p2--;
            }
            if(p0>p2){
                break;
            }

        }

    }

    private void cas(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}
